package practice_2025_9.practice_9_10;

class Solution {
    /**
     * 最长公共子序列
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j]: text1 以 i 为结尾, text2 以 j 为结尾的最长公共子序列
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        text1 = " " + text1;
        text2 = " " + text2;
        // 初始化
        // 填表
        int max = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    /**
     * 最小覆盖子串
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        // s 中涵盖 t 所有字符的最小子串 -> 子串中字符数量 >= t 中字符数量
        if (s.length() < t.length()) {
            return "";
        }
        int[] hashT = new int[128];
        int[] hashS = new int[128];
        for(char ch: t.toCharArray()) {
            hashT[ch]++;
        }
        int count = 0;
        int sz = t.length();
        int begin = -1;
        int len = Integer.MAX_VALUE;
        for(int left = 0, right = 0; right < s.length(); right++) {
            // 入窗口
            int in = s.charAt(right);
            hashS[in]++;
            if (hashS[in] <= hashT[in]) {
                count++;
            }
            // 更新 + 出窗口
            while (count == sz) {
                if (right - left + 1 < len) {
                    begin = left;
                    len = right - left + 1;
                    // System.out.println("left: " + left + " len: " + (right - left + 1));
                }
                int out = s.charAt(left);
                hashS[out]--;
                if (hashS[out] < hashT[out]) {
                    count--;
                }
                left++;
            }
        }
        if (begin < 0) {
            return "";
        } else {
            return s.substring(begin, begin + len);
        }
    }
}